package day1;

public class Hello {

	int fib(int n) {
		if (n <= 1) {
			return 1;
		}
		return fib(n - 1) + fib(n - 2);
	}

	public static void main(String[] args) {
		Hello h = new Hello();
//		int i = 4;
//		System.out.println(h.fib(5));
		Long start2 = System.currentTimeMillis();
		System.out.println(h.power(5d, 1000));
		Long end2 = System.currentTimeMillis();
		System.out.println(end2 - start2);
		Long start1 = System.currentTimeMillis();
		System.out.println(h.fpower(5d, 1000));
		Long end1 = System.currentTimeMillis();
		System.out.println(end1 - start1);
//		System.out.println(h.fib(1, 0, 5));
		Long start = System.currentTimeMillis();
		System.out.println(h.gpower(5d, 1000, 1d));
		Long end = System.currentTimeMillis();
		System.out.println(end - start);
	}

	double power(double m, int n) {
		double result = 1d;
		for (int i = 0; i < n; i++) {
			result *= m;
		}
		return result;
	}

	int fib(int a, int b, int n) {
		if (n == 0) {
			return a;
		} else {
			return fib(a + b, a, n - 1);
		}
	}

	double gpower(double m, int n, Double z) {

		double result = z;
		if (n <= 0)
			return result;
		result = m * result;
		return gpower(m, n - 1, result);
	}

	double fpower(double m, int n) {

		double result = 1d;
		double t = m;
		// 加法改成了位运算？
		for (int i = 1; i <= n; i <<= 1) {
			if ((i & n) > 0)
				result *= t;
			t *= t;
		}
		return result;
	}

}
